# -*- coding: utf-8 -*-
'''
python源码实现knn
'''
import os
import operator
import numpy as np

testFiles = os.listdir(".//data//testDigits")
trainingFiles = os.listdir(".//data//trainingDigits")

def img2vector(filename):
    vect = np.zeros((1,1024))
    fr = open(filename)
    for i in range(32):
        line = fr.readline()
        for j in range(32):
            vect[0,32*i+j] = int(line[j])
    fr.close()
    return vect


def getData(filelist, DigitsName):
    labels = []
    m = len(filelist)
    Mat = np.zeros((m,1024))
    for i in range(m):
        fileName = '.\\data\\'+DigitsName+'\\' + filelist[i]
        labels.append(filelist[i].split('_')[0])
        Mat[i,:] = img2vector(fileName)
    return labels, Mat


# 标准化数据（这里不需要这么做）
def autoNorm(dataSet):
    "Min-Max标准化"
    minVals = dataSet.min(0)
    maxVals = dataSet.max(0)
    ranges = maxVals - minVals
    normDataSet = np.zeros(np.shape(dataSet))
    m = dataSet.shape[0]
    normDataSet = dataSet - np.tile(minVals, (m,1))
    normDataSet = normDataSet/np.tile(ranges, (m,1))
    return normDataSet


# 预测分类    
def classify(inputX, dataSet, labels, k):
    dataSetSize = dataSet.shape[0]
    diffMat = np.tile(inputX, (dataSetSize, 1)) - dataSet
    sqDiffMat = diffMat ** 2
    sqDistances = sqDiffMat.sum(axis=1)
    distances = sqDistances**0.5
    sortedDistIndicies = distances.argsort() # 返回的是数组值从小到大的索引值 
    classCount = {}
    for i in range(k):
        voteIlabel = labels[sortedDistIndicies[i]]
        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
    sortedClassCont = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
    return sortedClassCont[0][0]
   
    
# 读取数据
trainingLabels, trainingMat = getData(trainingFiles, 'trainingDigits')
testLabels, testMat = getData(testFiles, 'testDigits')

K = 3
rightLabels = 0
for i in range(len(testLabels)):
    label = classify(testMat[i], trainingMat, trainingLabels, K)
    if label == testLabels[i]:
        rightLabels += 1

rate = rightLabels/len(testLabels) *100
print("K=%d时, 准确率是%.2f" % (K, rate))
    
    
    
    
    
    
    
    
    
    
    
    

